package cn.kingshion.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class ShellSort {
    public static void main(String[] args) {
        //随机化一个大容量的数组。
        //用来测试冒泡排序的效率
        int arr[] = new int[80000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 80000);
        }
        //定义一个时间对象，用来表示数组排序前的时间
        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        System.out.println("排序前：" + simpleDateFormat.format(date1));
        //排序数组
        shellSortReview(arr);
        System.out.println(Arrays.toString(arr));
        //新的时间，打印出排序完的时间
        Date date2 = new Date();
        System.out.println("排序前：" + simpleDateFormat.format(date2));
//        int arr[] = {5,59,84,6,8,16,16,4,891,6518,5,15,51,56,885,5,145};
//        shellSort(arr);
    }


    /**
     * 优化版的shell排序
     * 思路
     *
     * @param arr
     */
    public static void shellSort(int[] arr) {
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];
                if (arr[j] < arr[j - gap]) {
                    while (j - gap >= 0 && temp < arr[j - gap]) {
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    arr[j] = temp;
                }
            }
        }
    }

    public static void shellSortReview(int[] arr) {
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                int value = i;
                int temp = arr[value];
                if (arr[value] < arr[value - gap]) {
                    while (value - gap >= 0 && temp < arr[value - gap]) {
                        arr[value] = arr[value - gap];
                        value -= gap;
                    }
                    arr[value] = temp;
                }
            }
        }

    }


    /**
     * 交换法希尔排序
     *
     * @param arr
     */
    public static void shellSort2(int[] arr) {
        int temp = 0;
        int count = 1;
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j + gap];
                        arr[j + gap] = arr[j];
                        arr[j] = temp;
                    }
                }
            }
        }
    }
}
